#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2019/11/21 09:26|09:26
# @Author  : yangdingyi
# @File    : 两数之和 II - 输入有序数组
# @Software: PyCharm
from typing import List


class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 1.枚举 O(n^2) tle N/A 超时
        # n = len(numbers)
        # for i in range(n):
        #     for j in range(i+1, n):
        #         if numbers[i] + numbers[j] == target:
        #             return [i + 1, j + 1]
        # return []
        # 2.枚举+二分查找 O(nlogn) accept 108ms 通过
        # n = len(numbers)
        #
        # def search(nums: List[int], left: int, right: int, tag: int) -> int:
        #     while left <= right:
        #         h = (left + right) // 2
        #         x = nums[h]
        #         if tag == x:
        #             return h
        #         elif tag < x:
        #             right = h - 1
        #         else:
        #             left = h + 1
        #     return -1
        # for i in range(n-1):
        #     j = search(nums=numbers, left=i+1, right=n-1, tag=target-numbers[i])
        #     if j >= 0:
        #         return [i + 1, j + 1]
        # return []
        # 3.双指针滑动检测 O(n) accept 80ms 通过
        n = len(numbers)
        left, right = 0, n-1
        while left < right:
            x = numbers[left] + numbers[right]
            if x == target:
                return [left + 1, right + 1]
            elif x < target:
                left += 1
            else:
                right -= 1
        return []


solve = Solution()

numbers = [2, 7, 11, 15]
target = 9
print(numbers)
print(solve.twoSum(numbers=numbers, target=target))
